1. Field
The present disclosure generally relates to packet routing within a computer network. More specifically, the present disclosure relates to techniques and systems for implementing an optimal routing protocol using fixed-length positional labels.
2. Related Art
Mobile Ad hoc NETworks (MANETs) are becoming increasingly popular as mobile computing becomes an integral part of the modern lifestyle. Furthermore, there are an increasing number of scientific applications for wireless sensor nodes, which employ MANETs as their communication framework. Unfortunately, MANETs frequently experience runtime issues associated with lossy links, constrained resources, and other complications due to node mobility. These runtime issues can create a challenge for successfully deploying MANETs capable of achieving a dependable performance level.
As with any network protocol, routing in MANETs is subject to various types of overhead, which can influence how a communication protocol is designed and implemented for a given MANET. These overhead considerations impose design tradeoffs, such as runtime performance versus signaling overhead, which need to be considered specifically for a given MANET application. For example, a MANET architect currently has to determine whether the MANET application could benefit from proactive routing (i.e., maintain path information for other nodes at all times), or reactive routing (i.e., determine routes only when they are needed), or if the MANET application requires a customized network protocol which combines proactive routing and reactive routing.
When implementing a routing protocol, network architects are typically concerned with methods for storing and disseminating path information. There are currently two dominant routing techniques implemented for computer networks. In a first routing technique, path information for reaching a destination node is placed within the packet header of a data packet. The packet header includes the locations (i.e., node identifiers) for all nodes in the path to the destination node. This technique is viable for small networks that do not form long acyclic paths, but suffers from overhead issues with networks that have a large node density and/or diameter. First, as the number of nodes in a network increases, the node identifiers for the nodes also need to increase in size. Second, as the network increases in size, the length of the header path will also increase. These two overhead issues can require a packet to increase in size, or require more packets for communicating a given amount of data, as the number of computing nodes in a computer network increases.
In a second routing technique, path information for reaching a destination node is stored at each node in the path. This technique can be implemented by constructing a decision table at each node which identifies a subsequent node along a path toward a given destination node. This technique is viable for small networks, but also suffers from overhead issues for large networks. First, large networks require large decision tables at each node. Second, large networks cause the nodes to experience a large signaling overhead for maintaining the network state information at each node. These two overhead issues can cause a memory overhead, or cause performance degradation at a respective node, as a network increases in size.